import java.util.Arrays;

public class Leet64 {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; i++)
            dp[i][0] = grid[i][0]+dp[i-1][0];
        for (int i = 1; i < grid[0].length; i++)
            dp[0][i] = grid[0][i]+dp[0][i-1];
        System.out.println(Arrays.deepToString(dp));
        for (int i = 1; i < grid.length; i++)
            for (int j = 1; j < grid[0].length; j++)
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        return dp[dp.length-1][dp[0].length-1];
    }
//    static int min;
//    public int minPathSum(int[][] grid) {
//        min = 100000000;
//        dfs(grid,0,0,0);
//        return min;
//    }
//    void dfs(int[][] grid, int i,int j,int num){
//        num+=grid[i][j];
//        if (i==grid.length-1&&j==grid[0].length-1){
//            min = Math.min(num,min);
//        }
//        if(i!=grid.length-1)
//            dfs(grid,i+1,j,num);
//        if(j!=grid[0].length-1)
//            dfs(grid,i,j+1,num);
//    }

}
